package cn.threecubic.sort;


import java.util.Arrays;

/**
 * 插入排序
 *
 * @author Terminator
 * @date 2021/10/14 10:47
 */
public class InsertionSort {
    public static void main(String[] args) {
        int[] data = {14, 33, 27, 10, 35, 19, 42, 44};
        System.out.println("插入排序,排序前：" + Arrays.toString(data));
        insertionSort(data);
        System.out.println("插入排序,排序后：" + Arrays.toString(data));
    }

    /**
     * 插入排序
     *
     * @param arr
     */
    public static void insertionSort(int[] arr) {
        int length = arr.length;
        // 假设第一个元素已经是排好序了的，故从第二个元素开始扫描
        for (int i = 1; i < length; i++) {
            // 记录待插入的目标元素值(用以比对前面的元素)和待插入的目标元素的起始下标(用以往前遍历)
            int dataTemp = arr[i];
            int indexTemp = i;

            // 移动并且覆盖，找到目标位置
            while (indexTemp > 0 && arr[indexTemp - 1] > dataTemp) {
                arr[indexTemp] = arr[indexTemp - 1];
                indexTemp--;
            }

            // 如果待插入的目标元素的起始下标有移动，则插入
            if (indexTemp != i) {
                arr[indexTemp] = dataTemp;
            }
        }
    }
}
